package 优先算法.递归_搜索与回溯.综合案列.字母大小写排列;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        List<String> ret = so.letterCasePermutation("a1b2");
        System.out.println(ret);
    }
}

class Solution {
    List<String> ret;

    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        dfs(s, 0, new StringBuilder());
        return ret;
    }

    public void dfs(String s, int pos, StringBuilder path) {
        if (pos == s.length()) {
            ret.add(path.toString());
            return;
        }

        char c = s.charAt(pos);


        // 处理字母，分别添加小写和大写
        if (Character.isLetter(c)) {
            path.append(Character.toLowerCase(c));
            // 继续递归小写
            dfs(s, pos + 1, path);
            // 撤销添加小写字符
            path.deleteCharAt(path.length() - 1);

            // 添加大写字符
            path.append(Character.toUpperCase(c));
            dfs(s, pos + 1, path);
            // 撤销添加大写字符
            path.deleteCharAt(path.length() - 1);
        } else {
            // 如果是数字，直接递归
            path.append(c);
            // 继续递归
            dfs(s, pos + 1, path);
            // ���销添加数字字符
            path.deleteCharAt(path.length() - 1);
        }
    }
}